//实现支持下列接口的「快照数组」- SnapshotArray： 
//
// 
// SnapshotArray(int length) - 初始化一个与指定长度相等的 类数组 的数据结构。初始时，每个元素都等于 0。 
// void set(index, val) - 会将指定索引 index 处的元素设置为 val。 
// int snap() - 获取该数组的快照，并返回快照的编号 snap_id（快照号是调用 snap() 的总次数减去 1）。 
// int get(index, snap_id) - 根据指定的 snap_id 选择快照，并返回该快照指定索引 index 的值。 
// 
//
// 
//
// 示例： 
//
// 输入：["SnapshotArray","set","snap","set","get"]
//     [[3],[0,5],[],[0,6],[0,0]]
//输出：[null,null,0,null,5]
//解释：
//SnapshotArray snapshotArr = new SnapshotArray(3); // 初始化一个长度为 3 的快照数组
//snapshotArr.set(0,5);  // 令 array[0] = 5
//snapshotArr.snap();  // 获取快照，返回 snap_id = 0
//snapshotArr.set(0,6);
//snapshotArr.get(0,0);  // 获取 snap_id = 0 的快照中 array[0] 的值，返回 5 
//
// 
//
// 提示： 
//
// 
// 1 <= length <= 50000 
// 题目最多进行50000 次set，snap，和 get的调用 。 
// 0 <= index < length 
// 0 <= snap_id < 我们调用 snap() 的总次数 
// 0 <= val <= 10^9 
// 
//
// Related Topics 设计 数组 哈希表 二分查找 👍 160 👎 0


package com.tyrone.leetcode.editor.cn;

import java.util.*;

public class SnapshotArrays {
    public static void main(String[] args) {
        SnapshotArray snapshotArray = new SnapshotArrays().new SnapshotArray(3);
//        int i1 = snapshotArray.binarySearch(Arrays.asList(0, 4, 5) );
//        System.out.println(i1);
        System.out.println();
//        System.out.println(snapshotArray.snap());
//        int i1 = snapshotArray.get(0, 0);
//        int i2 = snapshotArray.get(0, 0);
//        snapshotArray.set(0, 2);
//        System.out.println(snapshotArray.snap());
//        snapshotArray.set(0, 14);
//        int i3 = snapshotArray.get(0, 1);
//        System.out.println(snapshotArray.snap());

//        System.out.println(snapshotArray.snap());
//        System.out.println(snapshotArray.snap());
//        snapshotArray.get(3,1);
//        snapshotArray.set(2,4);
//        System.out.println(snapshotArray.snap());
//        snapshotArray.set(1,4);
//

        snapshotArray.set(1, 6);
        System.out.println(snapshotArray.snap());
        System.out.println(snapshotArray.snap());
        snapshotArray.set(1, 19);
        snapshotArray.set(0, 4);
        snapshotArray.get(2, 1);
        snapshotArray.get(2, 0);
        int i = snapshotArray.get(0, 1);
        System.out.println(i);


//        int i1 = snapshotArray.get(1, 1);
//
//        int i2 = snapshotArray.get(1, 0);
//        snapshotArray.set(1, 3);
//        int i3 = snapshotArray.get(1, 0);
        snapshotArray.set(0, 5);
        System.out.println("ss");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class SnapshotArray {

        int version = 0;
        TreeMap<Integer, Integer>[] arr;

        public SnapshotArray(int length) {
            arr = new TreeMap[length];
            for (int i = 0; i < arr.length; i++) {
                TreeMap<Integer, Integer> map = new TreeMap<>();
                map.put(0, 0);
                arr[i] = map;
            }
        }

        public void set(int index, int val) {
            arr[index].put(version, val);
        }

        public int snap() {
            return version++;
        }

        public int get(int index, int snap_id) {
            TreeMap<Integer, Integer> map = arr[index];

            Integer key = map.floorKey(snap_id);
            return key == null ? 0 : map.get(key);
        }

        private int binarySearch(List<Integer> list, int target) {
            if (list == null || list.size() == 0) {
                return -1;
            }

            int left = 0;
            int right = list.size() - 1;
            int result = -1;

            while (left <= right) {
                int mid = left + (right - left) / 2;

                if (list.get(mid) <= target) {

                    result = list.get(mid);
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            return result == -1 ? 0 : result;
        }

    }

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray obj = new SnapshotArray(length);
 * obj.set(index,val);
 * int param_2 = obj.snap();
 * int param_3 = obj.get(index,snap_id);
 */
//leetcode submit region end(Prohibit modification and deletion)

}